Skip to main content

Coin Change

LeetCode 322 | Difficulty: Medium​

Medium

Problem Description​

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

- `1 <= coins.length <= 12`

- `1 <= coins[i] <= 2^31 - 1`

- `0 <= amount <= 10^4`

Topics: Array, Dynamic Programming, Breadth-First Search

Approach​

Dynamic Programming​

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

BFS (Graph/Matrix)​

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Solutions​

Complexity Analysis​

ApproachTimeSpace
Dynamic Programming$O(n)$$O(n)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.
  • Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
  • Consider if you can reduce space by only keeping the last row/few values.